package com.zjsru.oneDay202211;

import java.util.Arrays;

/**
 * @Author: CookLee
 * @Date: 2022/11/19
 * 找到最高海拔
 *
 * 输入：gain = [-5,1,5,0,-7]
 * 输出：1
 * 解释：海拔高度依次为 [0,-5,-4,1,1,-6] 。最高海拔为 1 。
 *
 * 输入：gain = [-4,-3,-2,-1,4,3,2]
 * 输出：0
 * 解释：海拔高度依次为 [0,-4,-7,-9,-10,-6,-3,-1] 。最高海拔为 0 。
 *
 */
public class LargestAltitude {
    
    /**
     * 模拟，运行内存和时间占比较大，需优化
     */
    public int largestAltitude(int[] gain) {
        int ans = 0;
        int[] nums = new int[gain.length + 1];
        nums[0] = ans;
        for (int i = 1; i < nums.length; i++) {
            nums[i] = ans + gain[i - 1];
            ans = nums[i];
        }
        return Arrays.stream(nums).max().getAsInt();
    }
    
    /**
     * 2 模拟,对时间优化100% 内存优化55%
     */
    public int largestAltitude2(int[] gain) {
        int cnt = 0, ans = 0;
        for (int num : gain) {
            cnt = cnt + num;
            ans = Math.max(cnt, ans);
        }
        return ans;
    }
    
    public static void main(String[] args) {
        LargestAltitude largestAltitude = new LargestAltitude();
        int[] gain = new int[]{-5,1,5,0,-7};
        System.out.println(largestAltitude.largestAltitude(gain));
    }
}
